#leetcode题目100：相同的树
#难度：简单

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p:
            return False
        if not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)


#测试数据
def create_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    queue = [root]
    i = 1
    while queue and i < len(values):
        node = queue.pop(0)
        if i < len(values) and values[i] is not None:
            node.left = TreeNode(values[i])
            queue.append(node.left)
        i += 1
        if i < len(values) and values[i] is not None:
            node.right = TreeNode(values[i])
            queue.append(node.right)
        i += 1
    return root

#测试
#测试用例1：相同的树
p = create_tree([1, 2, 3])
q = create_tree([1, 2, 3])
solution = Solution()
print(solution.isSameTree(p, q))  # 预期输出：True

#测试用例2：不同的树
p = create_tree([1, 2])
q = create_tree([1, None, 2])
solution = Solution()
print(solution.isSameTree(p, q))  # 预期输出：False

#测试用例3：都为空
solution = Solution()
print(solution.isSameTree(None, None))  # 预期输出：True